//You are given a string s that consists of lower case English letters and brack
//ets. 
//
// Reverse the strings in each pair of matching parentheses, starting from the i
//nnermost one. 
//
// Your result should not contain any brackets. 
//
// 
// Example 1: 
//
// 
//Input: s = "(abcd)"
//Output: "dcba"
// 
//
// Example 2: 
//
// 
//Input: s = "(u(love)i)"
//Output: "iloveu"
//Explanation: The substring "love" is reversed first, then the whole string is 
//reversed.
// 
//
// Example 3: 
//
// 
//Input: s = "(ed(et(oc))el)"
//Output: "leetcode"
//Explanation: First, we reverse the substring "oc", then "etco", and finally, t
//he whole string.
// 
//
// Example 4: 
//
// 
//Input: s = "a(bcdefghijkl(mno)p)q"
//Output: "apmnolkjihgfedcbq"
// 
//
// 
// Constraints: 
//
// 
// 0 <= s.length <= 2000 
// s only contains lower case English characters and parentheses. 
// It's guaranteed that all parentheses are balanced. 
// 
// Related Topics 栈 
// 👍 160 👎 0

package leetcode.editor.cn;

import org.junit.Assert;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

class P1190ReverseSubstringsBetweenEachPairOfParentheses {
    public static void main(String[] args) {
        Solution solution = new P1190ReverseSubstringsBetweenEachPairOfParentheses().new Solution();
        Assert.assertEquals(solution.reverseParentheses("vdgzyj()"),
                "apmnolkjihgfedcbq");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String reverseParentheses(String s) {
            Stack<StringBuilder> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c != ')') {
                    stack.push(new StringBuilder(c + ""));
                } else {
                    StringBuilder start = stack.pop().reverse();
                    if (!start.toString().equals("(")) {
                        while (!stack.isEmpty() && !stack.peek().toString().equals("(")) {
                            start.append(stack.pop().reverse());
                        }
                        stack.pop();
                        stack.push(start);
                    }

                }
            }
            StringBuilder res = new StringBuilder();

            while (!stack.isEmpty()) {
                res.insert(0, stack.pop());

            }
            return res.toString();
        }

        public String reverseParentheses1(String s) {
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c != ')') {
                    stack.push(c);
                } else {
                    Queue<Character> queue = new ArrayDeque<>();
                    while (!stack.peek().toString().equals("(")) {
                        queue.offer(stack.pop());
                    }
                    stack.pop();
                    while (!queue.isEmpty()) {
                        stack.push(queue.poll());
                    }
                }
            }
            StringBuilder res = new StringBuilder();
            while (!stack.isEmpty()) {
                res.insert(0, stack.pop());

            }
            return res.toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}